/*
 * Nancy Qiannan Zhang
 * Andrew ID: qiannanz
 * 
 * Mita Yipeng Yun
 * Andrew ID: yipengy
 */

package edu.cmu.cs211.bacon.util;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;


/**
 * An implementation of the minimum-spanning tree algorithm based on Kruskal's algorithm.
 * Only works on undirected graphs.
 */
public class Kruskal implements GraphMST {
	public <V,E extends Edge<V>> List<E> spanningTree(Graph<V,E> g) {
		if(g == null)
			throw new NullPointerException();
		//this is the list that contain result
		List<E> res = new ArrayList<E>();
		//the list of all the vertices
		ArrayList<V> vertexlist = new ArrayList<V>();
		vertexlist.addAll(g.vertices());
		//the sorted edges list
		//TreeSet<E> edges = new TreeSet<E>(new edge_comp<V>());
		List<E> edges = new ArrayList<E>();
		//iterate to add all the edges to the list
		Iterator<V> itr = vertexlist.iterator();
		while(itr.hasNext()){
			Collection<E> tt = g.outgoingEdges(itr.next());
			edges.addAll(tt);
		}
		Collections.sort(edges,new edge_comp<V>());
		Iterator<E> itr_edge = edges.iterator();
		UnionFind<V> uf = new UnionFind<V>(vertexlist);
		//iterate through to union vertices and add edges to res
		while(itr_edge.hasNext())
		{
			E temp = itr_edge.next();
			//if they won't create a cycle add to res
			if(!(uf.find(temp.src()).equals(uf.find(temp.dest())))){
				res.add(temp);
				uf.union(temp.src(), temp.dest());
			}
		}
		if(res.size()!=vertexlist.size()-1)
			return null;
		return res;
	}
	//the comparator used by treeSet
	private static class edge_comp<V> implements Comparator<Edge<V>>, Serializable{
		/**
		 * 
		 */
		private static final long serialVersionUID = 1L;

		public int compare(Edge<V> edge1, Edge<V> edge2){
			double res = edge1.weight()-edge2.weight();
			if(res>0)
				return 1;
			if(res<0)
				return -1;
			return 0;
		}
	}
}